/*
 * @lc app=leetcode.cn id=79 lang=javascript
 *
 * [79] 单词搜索
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let dfs = function (line, j, i) {
    if (i == len) {
      flag = true;
      return;
    }
    if (board[line][j - 1] == word[i]) {
      if(flag)return
      board[line][j - 1] = false;
      dfs(line, j - 1, i + 1);
      board[line][j - 1] = word[i];
    }
    if (board[line][j + 1] == word[i]) {
      if(flag)return
      board[line][j + 1] = false;
      dfs(line, j + 1, i + 1);
      board[line][j + 1] = word[i];
    }
    if (line - 1 >= 0 && board[line - 1][j] == word[i]) {
      if(flag)return
      board[line - 1][j] = false;
      dfs(line - 1, j, i + 1);
      board[line - 1][j] = word[i];
    }
    if (line + 1 < board.length && board[line + 1][j] == word[i]) {
      if(flag)return
      board[line + 1][j] = false;
      dfs(line + 1, j, i + 1);
      board[line + 1][j] = word[i];
    }
  };
  let len = word.length;
  let flag = false;
  for (let i = 0; i < board.length; i++) {
    for (let index = 0; index < board[0].length; index++)
      if (board[i][index] == word[0]) {
        board[i][index] = false;
        dfs(i, index, 1);
        board[i][index]=word[0]
      }
  }
  return flag;
};
// @lc code=end
exist(
  [
    ["A", "B", "C", "E"],
    ["S", "F", "E", "S"],
    ["A", "D", "E", "E"],
  ],
  "SEE"
);
